Packet-switched networks are known to have bursty traffic patterns. Network nodes (i.e., switches and routers) use memory buffers to store packets when traffic bursts cause packets to be received at a faster rate than they can be processed. Many traffic control techniques, such as rate shaping, rate limiting, and weighted random early drop (WRED), are used in conjunction with memory buffers to deal with bursty traffic.
On the output side of a network node, memory buffers are often used to temporarily store packets when packets are passing through the network node faster than the packets can be transmitted out onto their intended output links. When a memory buffer serves only a single output link, packets are typically dispatched from the buffer in a simple first-in first-out (FIFO) manner.
Because of the bursty nature of packet-switched traffic and because buffer memory is relatively expensive, buffer memory is often shared among multiple output links of a network node. For example, FIG. 1 depicts a switch module 102 that includes three output links 104 (output links A, B, and C) and a shared memory buffer 106 that is shared among the three output links. The switch module also includes a rate controller 108 that controls the rate at which packets 110 are written into the memory buffer. Even though the memory buffer is shared among multiple output links, packets are stored within the buffer and dispatched from the buffer on a FIFO basis. Referring to FIG. 1 for example, the packet that is at the head of the shared FIFO buffer (packet B1) must be dispatched to its intended output link (output link B) before the next packet in the shared FIFO buffer can be dispatched to its intended output link. While this technique works well if the output links are always available to transmit packets, the technique creates a head-of-line blocking problem in the shared FIFO buffer when the intended output link of the head packet is unavailable for transmission.
FIG. 2 depicts the head-of-line blocking problem that occurs when the head packet in a shared FIFO buffer is intended for an output link that is unavailable for transmission. In the example depicted in FIG. 2, output link B is unavailable for transmission and because the head packet is intended for the unavailable output link, the packets in the buffer that are intended for output links A (packets A1, A2, A3, and A4) and C (packets C1, C2, and C3) are blocked by the head packet. That is, the packets that are intended for output links A and C are blocked from being transmitted by the head packet, which is intended for the unavailable output link B, even though output links A and C are available for transmission.
Traditional packet-switched network nodes were not designed to ensure that all of the packets from the same flow are forwarded in the same order that they are received. However, as packet-switched networks begin to carry more time-sensitive traffic, such as voice and real-time video traffic, it is important that packets from the same flow of packets (i.e., all of the “A” packets in the FIFO buffer of FIG. 2) be transmitted from a network node in the same order that they are received. When packets are dispatched from a memory buffer on a strict FIFO basis, the order of the packets from the same flow is automatically preserved. For example, as long as the packets 110 shown in FIG. 2 are dispatched on a FIFO basis, the order of the packets related to each output link is maintained. Although the strict FIFO technique preserves the order of the packets, it leads to the head-of-line blocking problem as described above.
In view of the importance of shared memory buffers in packet-switched networks, what is needed is a technique for dispatching packets from a shared memory buffer that eliminates head-of-line blocking and maintains the order of packets from each flow.